// 有序矩阵中第K小的元素
// Created by madison on 2022/9/24.
//


#include "vector"
#include "queue"

using namespace std;

class Solution {
public:
    // 方法一：直接排序
    int kthSmallest(vector<vector<int>> &matrix, int k) {
        vector<int> rec;
        for (auto &row: matrix) {
            for (int it: row) {
                rec.push_back(it);
            }
        }
        sort(rec.begin(), rec.end());
        return rec[k - 1];
    }

    // 方法二：归并排序
    int kthSmallest1(vector<vector<int>> &matrix, int k) {
        struct point {
            int val, x, y;

            point(int val, int x, int y) : val(val), x(x), y(y) {}

            bool operator>(const point &a) const { return this->val > a.val; };
        };

        priority_queue<point, vector<point>, greater<>> que;
        int n = matrix.size();
        for (int i = 0; i < n; ++i) {
            que.emplace(matrix[i][0], i, 0);
        }
        for (int i = 0; i < k - 1; ++i) {
            point now = que.top();
            que.pop();
            if (now.y != n - 1) {
                que.emplace(matrix[now.x][now.y + 1], now.x, now.y + 1);
            }
        }
        return que.top().val;
    }
};

int main() {
    return 0;
}